#need UnionFind.py
def mst_kruskal(G,n): #n is number of nodes
    A = []
    V = xrange(n)
    UF= Disjoint_sets()
    for v in V:
        UF.makeset(v)
    G.sort(key = lambda (e,w): w)
    for ew in G:
        (u,v), _ = ew
        if UF.find_set(u) != UF.find_set(v):
            A.append((u,v))
            UF.union(u,v)
    return A

if __name__=='__main__':
    from UnionFind import Disjoint_sets
    import pprint
    G=[((0,1),4),((0,7),8),((1,2),8),((1,7),11),((2,3),7), \
       ((2,5),4),((2,8),2),((3,4),9),((3,5),14),((4,5),10), \
       ((5,6),2),((6,7),1),((6,8),6),((7,8),7)] #CLRS pp.568
    print 'Graph: e=(u,v),w'
    pprint.pprint(G)
    A = mst_kruskal(G,9)
    print 'MST: ', A
